
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;

public class Solver {

    public static ArrayList<Point> results = new ArrayList<Point>();
    private static EventQueue q;
    private static EventStatus t;
    private static Line home;
    
    public static void findIntersections(ArrayList<Line> segments) throws Exception {
        int cpt = 0;
        q = new EventQueue();
        t = new EventStatus();
        initEventQueue(segments, q);
        EventPoint actual = q.getFirstNode(q.root, null, false);
        while (actual != null) {
            handleEventPoint(actual);
            actual = q.getSuccessor(actual);
            cpt++;
        }
        
        System.out.println("Root : " + t.root.data);
        System.out.println("Compteur : " + cpt);
        System.out.println("Results : " + results.size());
        for(Point point: results)
            System.out.println("Point d'event : " + point.toString());
    }
    
    public static void handleEventPoint(EventPoint p) {
        // On suppose U, L et C connus dans p - pas besoin de parcourir T.
        ArrayList<Line> u = p.u_list, l = p.l_list, c = p.c_list;
        Point point = p.point;
        if(u.size() + l.size() + c.size() > 1)
            results.add(p.point);
        
        System.out.println("New Step  -  " + point);
        
        for(Line old_line : l)
            t.removeAVL(t.root, null, false, old_line);
            
        for(Line old_line : l)
            System.out.println("L " + old_line.toString());
        for(Line old_line : c)
            t.removeAVL(t.root, null, false, old_line);
        for(Line old_line : c)
            System.out.println("C " + old_line.toString());
        for(Line insertion : u)
            t.insertAVL(t.root, null, false, insertion);
        for(Line old_line : u)
            System.out.println("U " + old_line.toString());
        /* Ordre de réinsertion des C assez bordelique
        * Modifier la line avec Y courant, sauver ancienne infos, changer le X comme il faut
        * insérer, remodifier line avec les infos sauvées. méthode bof~correcte mais facile.
        */
        for(Line reinsertion : c) {
            Point save = (Point) reinsertion.p1.clone();
            reinsertion.p1.setLocation(point);
            t.insertAVL(t.root, null, false, reinsertion);
            reinsertion.p1.setLocation(save);
        }

        if(u.size() + c.size() == 0) {
            //System.out.println("Path #1");
            Line[] neighboors = t.getNeightbors2(point);
            if(neighboors != null)
                findNewEvent(neighboors[0], neighboors[1], point);
        } else {
            //System.out.println("Path #2");
            Line s1 = t.getLeftmostSegment(t.root, point, null);
            //System.out.println("Test #1 " + s1);
            if(s1 != null) {
                Line sl = t.getAVLPredecessor(t.root, s1);
                //System.out.println("Test #1' " + sl);
                if(sl != null) {
                    //EventPoint ev = findNewEvent(s1, sl, point);
                    EventPoint ev2 = findNewEvent(sl, s1, point);
                    //if((ev != null && ev2 == null) || (ev == null && ev2 != null) || (ev != null && ev2 != null && !ev.point.equals(ev2.point))) System.out.println("WOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOW");
                }
            }
            Line s2 = t.getRightmostSegment(t.root, point, null);
            //System.out.println("Test #2 " + s2);
            if(s2 != null) {
                Line sr = t.getAVLSuccessor(t.root, s2);
                //System.out.println("Test #2' " + sr);
                if(sr != null) {
                    findNewEvent(s2, sr, point);
                    //findNewEvent(sr, s2, point);
                }
            }
        }/**/
    }
    
    public static EventPoint findNewEvent(Line sl, Line sr, Point p) {
        if(sl.intersectsLine(sr)) {
            double[] coeffs1 = sl.getCoefficents();
            double[] coeffs2 = sr.getCoefficents();
            
            double x, y;
            if(coeffs1.length == 2 && coeffs2.length == 2) {
                x = (-(coeffs1[1] - coeffs2[1])) / (coeffs1[0] - coeffs2[0]);
                y = coeffs1[0] * x + coeffs1[1];
            } else if(coeffs1.length == 1 && coeffs2.length == 2) {
                x = coeffs1[0];
                y = coeffs2[0] * x + coeffs2[1];
            } else if(coeffs1.length == 2 && coeffs2.length == 1) {
                x = coeffs2[0];
                y = coeffs1[0] * x + coeffs1[1];
            } else {
                if(coeffs1[0] == coeffs2[0] && (sl.getY1() == sr.getY1() || sl.getY2() == sr.getY2())) {
                    x = coeffs1[0];
                    if(sl.getY1() == sr.getY1())
                        y = sl.getY1();
                    else
                        y = sl.getY2();
                } else {
                   /* Infinité d'intersection sur une portion des segments
                    * non géré
                    */
                    return null;
                }
            }
            Point new_point = new Point(x,y);
            
            if(p.compareTo(new_point) == 1) {
                EventPoint ev_point = new EventPoint(new_point);
                ev_point.c_list.add(sl);
                ev_point.c_list.add(sr);
                q.insert(ev_point);
                return ev_point;
            }
            else {
                System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++");
                System.out.println("Point d'event : " + p);
                System.out.println("new_point : " + new_point);
            }
            return new EventPoint(new_point);
        }
        return null;
    }

    private static void initEventQueue(ArrayList<Line> segments, Avl eventQueue) throws Exception {
        for(Line segment: segments){
            Point p1 = segment.getP1();
            Point p2 = segment.getP2();
            if(p1.getY() > p2.getY() || (p1.getY() == p2.getY() && p1.getX() <= p2.getX())){
                //TODO je pense qu'il faut rien faire de spécial.
            }
            else{ //if(p1.getY() < p2.getY() || (p1.getY() == p2.getY() && p1.getX() > p2.getX()))
                segment.setP1(p2);
                segment.setP2(p1);
            }
            EventPoint start_event = new EventPoint(segment.getP1());
            start_event.u_list.add(segment);
            q.insertAVL(q.root, null, false, start_event);
            EventPoint end_event = new EventPoint(segment.getP2());
            end_event.l_list.add(segment);
            q.insertAVL(q.root, null, false, end_event);
        }
    }
}
